package com.linjinp.study.算法;

import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

/**
 * 归并排序，fork/join 实现
 * @Author: linjinp
 * @Date: 2021/6/3 9:32
 */
public class MergeSort extends RecursiveTask<int[]> {

    // 数组
    private int[] src;
    // 开始索引
    private int beginInedx;
    // 结束索引
    private int endInedx;
    // 分片大小
    private int shard;

    public MergeSort(int[] src, int beginInedx, int endInedx, int shard) {
        this.src = src;
        this.beginInedx = beginInedx;
        this.endInedx = endInedx;
        this.shard = shard;
    }

    @Override
    protected int[] compute() {
        if (endInedx - beginInedx <= shard) {
            // 取出小分片
            int[] shardArray = splitArray(src, beginInedx, endInedx);
            // 对每个最小分片单位进行升序排序
            // 至少两个以上的值才进行排序
            if (endInedx - beginInedx >= 1) {
                bubblingSort(shardArray);
            }
            return shardArray;
        } else {
            // 继续从中间进行切分
            int mid = (beginInedx + endInedx) / 2;
            // 切分出左右两个分片
            MergeSort left = new MergeSort(src, beginInedx, mid, shard);
            MergeSort right = new MergeSort(src, mid + 1, endInedx, shard);
            invokeAll(left, right);
            int[] result = mergeArray(left.join(), right.join());
            return result;
        }
    }

    /**
     * 数组截取
     * @param src
     * @param beginInedx
     * @param endInedx
     * @return
     */
    private static int[] splitArray(int[] src, int beginInedx, int endInedx) {
        int[] shardArray = new int[endInedx - beginInedx + 1];
        int tmp = 0;
        for (int i = beginInedx; i <= endInedx; i++) {
            shardArray[tmp] = src[i];
            tmp ++;
        }
        return shardArray;
    }

    /**
     * 范围冒泡排序
     * @param src
     * @return
     */
    private static int[] bubblingSort(int[] src) {
        // 需要提前一位结束
        for (int i = 0; i < src.length; i++) {
            for (int j = i + 1; j < src.length; j++) {
                if (src[i] > src[j]) {
                    int tmp = src[i];
                    src[i] = src[j];
                    src[j] = tmp;
                }
            }
        }
        return src;
    }

    /**
     * 数组合并
     * @param arr1
     * @param arr2
     * @return
     */
    private static int[] mergeArray(int[] arr1, int[] arr2) {
        // 创建新数组
        int[] result = new int[arr1.length + arr2.length];
        // 对两个合并数组的索引进行记录
        int index1 = 0;
        int index2 = 0;
        // 最终数组索引记录
        int index = 0;
        for (;;) {
            // 如果新数组已经填满，结束循环
            if (index == result.length) {
                break;
            }
            // 两个数组都没越界的情况下，比较入队
            if (index1 < arr1.length && index2 < arr2.length) {
                if (arr1[index1] <= arr2[index2]) {
                    result[index] = arr1[index1];
                    index1 ++;
                } else {
                    result[index] = arr2[index2];
                    index2 ++;
                }
                index++;
            } else {
                // 如果是 arr1 数组越界了，把剩下的 arr2 数组顺序入队
                if (index1 >= arr1.length) {
                    for (; index2 < arr2.length; index2++) {
                        result[index] = arr2[index2];
                        index++;
                    }
                } else {
                    // 如果是 arr2 数组越界了，把剩下的 arr1 数组顺序入队
                    for (; index1 < arr1.length; index1++) {
                        result[index] = arr1[index1];
                        index++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        ForkJoinPool pool = new ForkJoinPool();
        int[] src = MakeArray.makeArray(10000);
        System.out.println("数据量：" + src.length);
        System.out.println("初始数组：" + Arrays.toString(src));

        long time1 = System.currentTimeMillis();
        System.out.println("冒泡排序开始时间：" + time1);
        int[] bubblingSort = bubblingSort(src.clone());
        long time2 = System.currentTimeMillis();
        System.out.println("冒泡排序结束时间：" + time2);
        System.out.println("冒泡排序时间：" + (time2 - time1));
        System.out.println("冒泡排序：" + Arrays.toString(bubblingSort));

        long time3 = System.currentTimeMillis();
        System.out.println("归并排序开始时间：" + time3);
        MergeSort sort = new MergeSort(src, 0, src.length - 1, 2);
        pool.invoke(sort);
        int [] result = sort.join();
        long time4 = System.currentTimeMillis();
        System.out.println("归并排序结束时间：" + time4);
        System.out.println("归并排序时间：" + (time4 - time3));
        System.out.println("归并排序：" + Arrays.toString(result));
    }

}
